СИНТЕЗ НАДЕЖНЫХ СХЕМ ПРИ КОНСТАНТНЫХ НЕИСПРАВНОСТЯХ                                  НА ВХОДАХ И ВЫХОДАХ ЭЛЕМЕНТОВ

Алехина Марина Анатольевна, доктор физико-математических наук, профессор, заведующая кафедрой дискретной математики, Пензенский государственный университет (Россия, г. Пенза, ул. Красная, 40), alehina@pnzgu.ru

519.718

Актуальность и цели. Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в базисе, состоящем из одной функции – штрих Шеффера. Задача синтеза надежных схем, реализующих булевы функции, при константных неисправностях одного типа (например, только типа 0 на входах элементов) решалась ранее автором во многих статьях, но, в отличие от них, в этой работе впервые исследуется модель, в которой каждый элемент схемы может быть подвержен константным неисправностям сразу четырех типов: типа 0 и типа 1 на входах и выходах (с различными вероятностями). Заметим также, что при подходящем выборе параметров эта модель описывает инверсные неисправности элементов на входах и (или) выходах. Цель работы – построить надежные схемы, получить верхние и нижние оценки ненадежности схем.
Материалы и методы. При построении надежных схем использованы ранее известные методы синтеза и получения оценок ненадежности.
Результаты. Получена верхняя оценка ненадежности схем. Описан класс функций K, содержащий почти все булевы функции, и доказана нижняя оценка ненадежности схем, реализующих функции из этого класса. Для функции из класса K построена схема, верхняя и нижняя оценки ненадежности которой асимптотически равны. Полученные результаты могут быть использованы при проектировании технических систем для повышения их надежности.
Выводы. Почти любую булеву функцию можно реализовать схемой, верхняя и нижняя оценки ненадежности которой асимптотически равны.

ненадежные функциональные элементы, надежность схемы, ненадежность схемы, константные неисправности типа 0 и 1 на входах и выходах элементов.

1. Neuman, von J. Probabilistic logics and the synthesis of reliable organisms from unreliable components / J. von Neuman // Automata studies / ed. by C. Shannon, Mc. Carthy. – Princeton : Princeton University Press, 1956. – P. 43–98.
2. Алехина, М. А. Синтез асимптотически оптимальных по надежности схем : моногр. / М. А. Алехина. – Пенза : Инф.-изд. центр ПензГУ, 2006. – 156 с.
3. Алехина, М. А. О ненадежности схем из функциональных элементов, подверженных двум типам неисправностей / М. А. Алехина, О. Ю. Барсукова // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. – 2013. – № 3 (27). – С. 31–47.
4. Грабовская, С. М. О надежности неветвящихся программ с ненадежным оператором условной остановки в произвольном полном конечном базисе / С. М. Грабовская // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. – 2011. – № 3 (19). – С. 52–60.
5. Alekhina, M. A. Synthesis and complexity of asymptotically optimal circuits with unreliable gates / M. A. Alekhina // Fundamenta Informaticae. – 2010. – Vol. 104 (3). – P. 219–225.